package io.zouyalong.algo.leetcode;

import java.util.Arrays;

/**
 * 题源
 * https://leetcode-cn.com/problems/trapping-rain-water/
 * 给定 n 个非负整数表示每个宽度为 1 的柱子的高度图，计算按此排列的柱子，下雨之后能接多少雨水
 */
public class TrappingRainWater {
    public static void main(String[] args) {
        int size = 100000;
        if (args.length > 1) {
            size = Integer.parseInt(args[1]);
        }
        var inst = new TrappingRainWater();
        int[] heights = inst.randomInput(size);
//        var heights = new int[]{0,1,0,2,1,0,1,3,2,1,2,1};
        System.out.printf("run: size=%d \n\theights=%s\n", size, Arrays.toString(heights));
        //
        var start = System.currentTimeMillis();
        var sum = inst.on2Solution(heights);
        System.out.printf("\ton2Solution(%d ms): %d\n", System.currentTimeMillis() - start, sum);
        start = System.currentTimeMillis();
        sum = inst.dualPointers(heights);
        System.out.printf("\tdualPointers(%d ms): %d\n", System.currentTimeMillis() - start, sum);
        start = System.currentTimeMillis();
        sum = inst.dp(heights);
        System.out.printf("\tdp(%d ms): %d\n", System.currentTimeMillis() - start, sum);
    }

    public int[] randomInput(int size) {
        int[] results = new int[size];
        for (int i = 0; i < size; i++) {
            results[i] = (int) (Math.random() * 10);
        }
        return results;
    }

    /**
     * 暴力法，时间复杂度 O(n2)
     *
     * @param height
     * @return
     */
    public int on2Solution(int[] height) {
        int sum = 0;
        int length = height.length;
        for (int current = 1; current < length - 1; current++) {
            int leftHeight = 0;
            int rightHeight = 0;
            for (int left = 0; left < current; left++) {
                if (height[left] >= leftHeight) {
                    leftHeight = height[left];
                }
            }
            for (int right = length - 1; right > current; right--) {
                if (height[right] >= rightHeight) {
                    rightHeight = height[right];
                }
            }
            int currentCap = Math.min(leftHeight, rightHeight) - height[current];
            if (currentCap > 0) {
                sum += currentCap;
            }
        }
        return sum;
    }

    public int dualPointers(int[] height) {
        // todo 有问题 [9,6,8,8,5,6,3] 输出 1，预期 3
        if (height.length == 0) {
            return 0;
        }
        int leftHighest = 0, leftHighestIndex = 0; // 左边已扫描的最高值
        int rightHighest = 0, rightHighestIndex = 0; // 右边已扫描的最高值
        int length = height.length;
        int left = 0, right = length - 1;
        int sum = 0;
        for (; left < right; left++, right--) {
            if (height[left] >= leftHighest) {//与左边已出现的最高点形成洼地
                for (int i = leftHighestIndex + 1; i < left; i++) {
                    sum += leftHighest - height[i];
                }
                leftHighest = height[left];
                leftHighestIndex = left;
            }
            if (height[right] >= rightHighest) {// 与右边已出现的最高点形成洼地
                for (int i = right + 1; i < rightHighestIndex; i++) {
                    sum += rightHighest - height[i];
                }
                rightHighest = height[right];
                rightHighestIndex = right;
            }
        }
        if (height[left] >= leftHighest) {
            for (int i = leftHighestIndex + 1; i < left; i++) {
                sum += leftHighest - height[i];
            }
            leftHighest = height[left];
            leftHighestIndex = left;
        }
//        System.out.printf("Current: left(%d) right(%d)\n", left, right);
//        System.out.printf("left: %d(%d), right: %d(%d)\n", leftHighest, leftHighestIndex, rightHighest, rightHighestIndex);
        int minHeight = Math.min(leftHighest, rightHighest);
        for (int i = leftHighestIndex + 1; i < rightHighestIndex; i++) {
            if (minHeight > height[i])
                sum += minHeight - height[i];
        }
        return sum;
    }

    public int dp(int[] height) {
        var size = height.length;
        var leftHighest = new int[size];
        var rightHighest = new int[size];
        for (int i = 1; i < size; i++) {
            leftHighest[i] = Math.max(height[i - 1], leftHighest[i - 1]);
        }
        for (int i = size - 2; i >= 0; i--) {
            rightHighest[i] = Math.max(height[i + 1], rightHighest[i + 1]);
        }
        int sum = 0;
        for (int i = 1; i < size; i++) {
            var diff = Math.min(leftHighest[i], rightHighest[i]) - height[i];
            if (diff > 0) {
                sum += diff;
            }
        }
        return sum;
    }

}
